#ifndef _BO2_5_H
#define _BO2_5_H

#include "c1.h"
#include "c2-3.h"
//bo2-5.h 静态链表 数据结构由c2-3.h定义   13个基本操作，包含了严书算法2.13~算法2.16
#define DestroyList ClearList //DestroyList()和ClearList()操作时一样的

int Malloc(SLinkList space) //算法2.15
{
    //若备用链表为非空，则返回分配的节点下标（备用链表的第一个结点）；否则返回0
    int i = space[0].cur; // 备用链表第一个节点的位置
    if(i)//如果备用链表非空
    {
        space[0].cur = space[i].cur;
    }
    return i;
}

void Free(SLinkList space, int k) //算法2.16
{//将下标为k的空闲结点回收到备用链表
    space[k].cur = space[0].cur; //回收节点的游标指向备用链表的第一个节点
    space[0].cur = k;
}

void InitList(SLinkList L)
{//构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE-1]，其余单元全部链成一个备用链表，表头为L的第一个单以L[0]，“0”表示“空指针”
    int i;
    L[MAX_SIZE - 1].cur = 0;//L的最后一个单元为空链表的表头
    for( i = 0; i < MAX_SIZE-2 ; i++) //将其余单元链接成以L[0]为表头的备用链表
        L[i].cur = i + 1;
    L[MAX_SIZE - 2].cur = 0;
}

void ClearList(SLinkList L)
{
    int j , i = L[0].cur;//i指向备用链表第一个节点的位序
    while(i) // 未到备用链表表尾
    {
        j = i; //j指示当前节点的位序
        i = L[i].cur;
    }
    L[j].cur = L[MAX_SIZE - 1].cur; //链表的第一个节点接到备用链表的尾部
    L[MAX_SIZE - 1].cur = 0; // 链表空
}

Status ListEmpty(SLinkList L)
{
    if(L[MAX_SIZE - 1].cur == 0)
        return TRUE;
    else
        return FALSE;
}

int ListLength(SLinkList L)
{
    int j = 0, i = L[MAX_SIZE - 1].cur; //指向链表的第一个节点的位序
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

Status GetElem(SLinkList L, int i , ElemType &e)
{
    int m , k = MAX_SIZE -1;
    if(i<1 || i > ListLength(L))
        return ERROR;
    for(m = 1; m <= i; m++)
    {
        k = L[k].cur;
    }
    e = L[k].data;
    return OK;
}

int LocateElem(SLinkList L , ElemType e)
{
    int i = L[MAX_SIZE -1].cur; // i指向第一个节点的位序
    while(i && L[i].data != e)
        i = L[i].cur;
    return i;
}

Status PriorElem(SLinkList L, ElemType cur_e, ElemType &pre_e)
{
    int j , i = L[MAX_SIZE - 1].cur;
    do
    {
        j = i;
        i = L[i].cur;
    }while(i && cur_e != L[i].data);
    if(i)
    {
        pre_e = L[j].data;
        return OK;
    }
    return ERROR;
}

Status NextElem(SLinkList L, ElemType cur_e, ElemType &next_e)
{
    int j , i = LocateElem(L, cur_e);
    if(i)
    {
        j = L[i].cur; //j指向cur——e的后继位置
        if(j) //cur_e有后继
        {
            next_e = L[j].data;
            return OK;
        }
    }
    return ERROR;
}

Status ListInsert(SLinkList L, int i , ElemType e)
{
    int m , j, k = MAX_SIZE -1;//k指向表头结点的位序
    if(i < 1 || i> ListLength(L)+1) //i不合法
        return ERROR;
    j = Malloc(L);
    if(j)
    {
        L[j].data = e;
        for(m = 1; m <i; m++) // k向后移动i-1个节点，使得k指向第i-1个节点
            k = L[k].cur;
        L[j].cur = L[k].cur; //新单元指向第i-1个元素后面的元素
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

Status ListDelete(SLinkList L, int i , ElemType &e)
{
    int j, k = MAX_SIZE -1;//k指向表头结点的位序
    if(i < 1 || i> ListLength(L)) //i不合法
        return ERROR;
    for(j = 1; j < i; j++) // 移动i-1个元素，使得k指向第i-1个元素
        k = L[k].cur;
    j = L[k].cur;//将待删除元素（第i个元素）的位置赋给j
    L[k].cur = L[j].cur; //让第i-1个元素指向待删除元素的后继元素
    e = L[j].data;
    Free(L , j); // 释放待删除节点（回收到备用链表中）
    return OK;
}

void ListTraverse(SLinkList L, void(*visit)(ElemType))
{
    int i = L[MAX_SIZE -1].cur;
    while(i)
    {
        visit(L[i].data);
        i = L[i].cur;
    }
    printf("\n");
}





#endif